Search results for "Higher-order logic"

showing 4 items of 4 documents

Monadic second-order logic over pictures and recognizability by tiling systems

1994

We show that a set of pictures (rectangular arrays of symbols) is recognized by a finite tiling system if and only if it is definable in existential monadic second-order logic. As a consequence, finite tiling systems constitute a notion of recognizability over two-dimensional inputs which at the same time generalizes finite-state recognizability over strings and matches a natural logic. The proof is based on the Ehrenfeucht-FraIsse technique for first-order logic and an implementation of “threshold counting” within tiling systems.

Predicate logicDiscrete mathematicsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESComputer Science::Logic in Computer ScienceSubstructural logicSecond-order logicMultimodal logicDynamic logic (modal logic)Intermediate logicHigher-order logicComputer Science::Formal Languages and Automata TheoryMonadic predicate calculusMathematics
researchProduct

Logics with counting and equivalence

2014

We consider the two-variable fragment of first-order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NEXPTIME-complete. We further show that the corresponding problems for two-variable first-order logic with counting and two equivalences are both undecidable.

Discrete mathematicsLogical equivalenceComplexityHigher-order logicSatisfiabilityUndecidable problemStipulationCombinatoricsBinary predicateTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESEquivalence relationComputer Science::Logic in Computer ScienceEquivalence relationSatisfiabilityEquivalence (formal languages)MathematicsProceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
researchProduct

Employing fuzzy logic in the diagnosis of a clinical case

2010

Fuzzy logic is a logical calculus which operates with many truth values (while classical logic works with the two values of true and false). Since fuzzy logic considers the truth of scientific statements like something softened, it is fruitfully applied to the study of biological phenomena, biology is indeed considered the field of complexity, uncertainty and vagueness. In this paper fuzzy logic is successfully applied to the clinical diagnosis of a patient who suffers from different diseases bound by a complex causal chain. In this work it is presented a mathematical foundation of fuzzy logic (with connectives and inference rules) and then the application of fuzzy reasoning to the study of…

business.industryProbabilistic logic networkMany-valued logicMultimodal logicDynamic logic (modal logic)Paraconsistent logicSettore M-FIL/02 - Logica E Filosofia Della ScienzaArtificial intelligenceT-norm fuzzy logicsbusinessFuzzy Logic Probabilistic Logic Clinical diagnosis Biological phenomena TruthHigher-order logicFuzzy logicHealth
researchProduct

Monadic Second-Order Logic over Rectangular Pictures and Recognizability by Tiling Systems

1996

Abstract It is shown that a set of pictures (rectangular arrays of symbols) is recognized by a finite tiling system iff it is definable in existential monadic second-order logic. As a consequence, finite tiling systems constitute a notion of recognizability over two-dimensional inputs which at the same time generalizes finite-state recognizability over strings and also matches a natural logic. The proof is based on the Ehrenfeucht–Fraisse technique for first-order logic and an implementation of “threshold counting” within tiling systems.

Predicate logicMonadic second-order logicDiscrete mathematicsNatural logicIntermediate logicHigher-order logicMonadic predicate calculusComputer Science ApplicationsTheoretical Computer ScienceMathematics::LogicTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESComputational Theory and MathematicsComputer Science::Logic in Computer ScienceMany-valued logicDynamic logic (modal logic)Computer Science::Formal Languages and Automata TheoryInformation SystemsMathematicsInformation and Computation
researchProduct